1. Field of the Invention
The present invention relates to a method and apparatus for optimizing route planning for vehicles. The invention is especially useful in reducing costs associated the “last mile” of a deliverable, although not limited to such use.
2. Background Discussion
In business and as is used in this disclosure, the “last mile” refers to the process of getting a deliverable (a service or product, e.g.) to a final customer or consumer (e.g. a package from a distribution center to a customer). In this context, the “last mile” does not refer to the last 5,280 feet traveled by the deliverable—the “last mile” of the deliverable may be significantly more or less than a mile. According to the Council of Logistics Management, in average, 28 percent of transportation costs are incurred in this so-called last mile, which greatly impacts a company's bottom line. The last mile is also a major concern to businesses as it strongly influences a customer's perception of a company. Because the last mile includes the final point of contact with customers, it greatly affects a customer's brand loyalty based on that customer's good or bad experience.
To improve the efficiency of last mile delivery, numerous conflicting constraints are involved, e.g., congestion on roads, delivery time requirements for different categories of mail, such as priority post, varying customer needs, real time notification to pick up a packet for upstream while engaged in downstream delivery, and so on. Though a flood of new technologies and services have cropped up in the past 10 years promising to streamline companies' supply chains, few solutions have sufficiently addressed the last mile delivery problem. Given the performance efficiency expected by the customers, versus cost-sensitiveness of the last mile, delivery agencies are quite logically seeking ways to reduce costs precisely at the distribution end. Thus there is a need to search for efficient delivery methods, rendering lower delivery costs, minimum delivery time, employing less number of carriers, and yet offer better service to customers.
Planning an optimum route for travel from an initial location (e.g. a distribution center) to multiple customer locations is an important aspect to reducing costs associated with the last mile. Some businesses where such optimum route planning is pertinent include postal delivery businesses (UPS, USPS, FedEx, DHL etc), other delivery businesses (e.g. WebVan, Sameday.com, for web orders, online grocery delivery, pizza delivery, etc), supply chain management companies, as well as businesses needing to visit multiple customers for solely service and/or sales purposes (e.g., a cable service company).
Many navigation systems for planning an optimum route between locations base calculations solely on static information, for example start and ending points provided by a user, and a database with road map information (fixed on a CD in the vehicle). Such systems are useful for providing directions, but are inadequate for optimizing route travel for many businesses desiring to reduce costs associated with the last mite. Many of these navigation systems do not have an optimum route planning algorithm capable of determining the optimum order of traveling to multiple desired locations, and instead can only choose the route between two locations (the starting location and the ending location). Further, since the route is calculated based on static information (the map information fixed on a CD e.g.), changes which may have occurred to such information (traffic patterns, e.g.) cannot be taken into account when planning the optimum route.
Systems for planning an optimum route using updated information are known. U.S. Pat. No. 6,745,123 relates to a method and a device for transmitting navigation information from a data processing center to an on-board navigation system. The updated navigation information may include information pertaining to, e.g., addition of a new road in the road network infrastructure, road closings due to constructions, parking services, general urban information, and availability of a new restaurants/hotels. Thus because the user receives updates over the air, it reduces the need to replace the entire storage medium (e.g., a purchase of a new CD ROM with an updated digital map).
U.S. Pat. No. 6,028,553 refers to a self-sufficient navigation system in combination with a GSM interface via which a current route can be requested. The self-sufficient navigation system can calculate the route to the desired destination, purely self-sufficiently on the basis of the static data on board. A presumed position at a time of an anticipated reply is transmitted to a central with an inquiry via a mobile radiotelephone network. The central can then check whether it is possible to travel over the indicated path segment. When the central finds that it is not possible to travel over the planned path segments, it calculates the route and a route recommendation is output to the vehicle as data. This is generally a sequence of path segments. Since the method involves transmitting a route's navigation information, it may have the disadvantage that very large volumes of data may be required to be transmitted, congesting a wireless network and incurring associated high wireless service fees.
U.S. Pat. No. 6,334,089 describes a vehicle-based navigation system located in a vehicle, and a central server located outside of the vehicle. The navigation system includes an input device by which at least one destination is input thereto, the central server includes means for determining a route or the vehicle from the at least one destination and means for transmitting the route determined from the at least one destination piecewise to the navigation system. Since the system also involves transmitting a route's navigation information, a large amount of data should be transferred, congesting a wireless network, resulting in high wireless service fees.
In United States Application 20020152018 relates to the problem of congesting wireless networks due to transmission of route information to the vehicle from a control center. Data required for optimized route planning, which must be transmitted from a traffic control center to a motor vehicle navigation system, is reduced to a lesser amount. Essentially only the information necessary for driving an alternative section of the original route is transmitted from a traffic control center to the vehicle navigation system. This information represents only deviations from the route calculated in the vehicle navigation system.
However, the navigation systems noted above are not suitable for many service vehicles as there is no ability of the navigations systems to determine the order of multiple destinations to obtain an optimum route between all of the desired destinations. Further, there is no mechanism taught to dynamically alter the destinations. Finally, there is a concern of congesting wireless networks in the communication of route data from a control center to the vehicle.